Autooptimización en esquemas paralelos iterativos (página 2)

Partes: 1, 2

El problema de Optimización

Objetivo: min t(s, vap, SP)?
vap ? AP

Asignación de procesadores a las necesidades software

Técnicas:

Grafos de precedencia

Optimización analítica

Árboles de asignación

Estrategias heterogéneas (HoHe, HeHo)?

Metaheurísticas

……

9

El problema de Optimización
Cuestiones relevantes:

Particionado de datos

Análisis de dependencias

Asignación de recursos

Equilibrado de carga

Hipótesis:

Construcc. sotfware
Modelado Autooptimización
tº ejecución

Necesidad de establecer una metodología de trabajo

10

Metodología Tesis
Etapas de la tesis

Construir modelo tº ejecución algoritmos iterativos
11

Metodología Tesis
Etapas de la tesis

Construir modelo tº ejecución algoritmos iterativos
Aplicaciones en esquemas paralelos iterativos
12

Metodología Tesis
Etapas de la tesis

Construir modelo tº ejecución algoritmos iterativos
Aplicaciones en esquemas paralelos iterativos
Desarrollo metodologías autoopt. sist. homogéneos
13

Metodología Tesis
Etapas de la tesis

Construir modelo tº ejecución algoritmos iterativos
Aplicaciones en esquemas paralelos iterativos
Desarrollo metodologías autoopt. sist. homogéneos
Desarrollo metodologías autoopt. sist. heterogéneos
14

Metodología Tesis
Etapas de la tesis

Construir modelo tº ejecución algoritmos iterativos
Aplicaciones en esquemas paralelos iterativos
Desarrollo metodologías autoopt. sist. homogéneos
Desarrollo metodologías autoopt. sist. heterogéneos
Estrategias heterogéneas
(HoHe, HeHo)?
15

Metodología Tesis
Etapas de la tesis

Construir modelo tº ejecución algoritmos iterativos
Aplicaciones en esquemas paralelos iterativos
Desarrollo metodologías autoopt. sist. homogéneos
Desarrollo metodologías autoopt. sist. heterogéneos
Estrategias heterogéneas
(HoHe, HeHo)?

Metaheurísticas

16

Metodología de autooptimización
17

Construcción modelo tº ejecución
18

Esquemas iterativos
Esquema iterativos usados en multitud de problemas: Progr.
Dinámica, Dijkstra, genéticos, sist. ecuaciones …

Ejecución de un conjunto de instrucciones de forma iterativa hasta la
condición de fin

Secuenciales
Tipos Homogéneos
Paralelos
Heterogéneos

Caso (Programación Diferentes
Prueba dinámica) Esquemas

Diferentes formas de calcular los datos: por filas, columnas,
diagonales

19

Programación dinámica
Por filas

20

Programación dinámica
Por filas

Por columnas

21

Programación dinámica
Por filas

Por columnas

Por diagonales

22

Programación dinámica
Usados como ejemplos: Problema monedas, Mochila

Definición
N: cantidad a devolver
n: número tipos de monedas
vi: valor de la moneda de tipo i, vi>0
qi: cantidad de monedas de tipo i, qi>0
c[i,j]= mínimo número de monedas para devolver cantidad j usando
hasta los i tipos de monedas

c[i,j] = min { c[i-1,j-k*vi]+k}, 1< =i< =n, 1< =j< =N, k=0,..,j/vi

Objetivo: c[n,N]

Ecuación
23

Esquema Secuencial

for i=1 to numero_de_decisiones
for j=1 to tamaño_problema
obtener la solución óptima
con i decisiones y
tamaño de problema j
endfor
endfor

Programación dinámica
24
FILAS

COLUMNAS

Esquema Paralelo (dependencia de datos)?

for i=1 to numero_de_decisiones
En Paralelo:
for j=1 to tamaño_problema
obtener la solución óptima
con i decisiones y
tamaño de problema j
endfor
Comunicaciones entre procesos
endEnParalelo
endfor

Esquemas iterativos
25

AUTOOPTIMIZACIÓN EN SISTEMAS HOMOGÉNEOS
26

Autooptimización en sistemas homogéneos
Homogéneos: características similares no exactamente iguales

Relativa facilidad construir modelo tiempo ejecución

Determinar número procesos (p) = procesadores (P)?

Pruebas realizadas sobre diferentes sistemas:

SOLARIS/SUN (SUNEt)? (Un. Murcia)?
PenFE (Un. Murcia) HOMOGÉNEOS
ORIGIN 2000 (Un. Polit. Cat.)
HPC160 (Inter e intranodo)? (Un. Polit. Cart.)?

KIPLING (Univ. Polit. Val.) HETEROGÉNEOS
TORC (Univ. Tennessee)?

27

Autooptimización en sistemas homogéneos
DEPENDENCIA DE DATOS (VERSIONES A y B)
28

Número procesadores Número procesadores
Complejidad Complejidad
Tamaño 10.000 Tamaño 50.000
Tamaño 100.000 Tamaño 500.000
Número procesadores Número procesadores
Cociente de tiempos de ejecución entre versiones A y B en SUNEt
Complejidad Complejidad
Autooptimización en sistemas homogéneos
29

Modelo teórico:
Ttotal = Tcomputación + Tcomunicación

Coste secuencial:

Coste computacional paralelo (qi grande):

Coste comunicaciones:

Parámetro de complejidad o granularidad para aumentar comput.

Los SP son tc , ts y tw

El único AP es p

(Gp:) Proceso Pp-1

Autooptimización en sistemas homogéneos
30

Diferentes posibilidades estimar parámetros sistema

Diferencias en speed-up Utilidad
de sistemas autooptimización

Autooptimización en sistemas homogéneos
31

Tiempos de comunicaciones en SUNEt (izq) y HPC160 (der)?
Ratios de tiempos de comunicaciones en SUNEt (izq) y HPC160 (der)?
Autooptimización en sistemas homogéneos
32

Comparativa entre el número de procesos con los que se obtiene mejor tiempo de ejecución
Autooptimización en sistemas homogéneos
33
El sistema debe decidir cómo ejecutar el algoritmo

Media de los speedups máximos variando tamaño y granularidad
Speedup variando procesadores, granularidad y tamaño
Autooptimización en sistemas homogéneos
34

Estimación de SP aritméticos: resolviendo un problema reducido

Estimación de SP de comunicac:

Ping-pong (CP1)?
Solución de problema reducido variando el número de procesadores (CP2)?
Solución de problema reducido variando el número de procesadores y el tamaño del problema (CP3)?

Comparativa del número de procesadores seleccionados con diferentes métodos con respecto al tmb
Autooptimización en sistemas homogéneos
35

Cocientes entre tiempos de ejecución obtenido con los diferentes métodos con respecto al tmb
Autooptimización en sistemas homogéneos
36

Comparación con usuarios:

Voraz (UV): usa todos los procesadores disponibles
Conservador (UC): usa la mitad de los procesadores disponibles
Experto (UE): usa un número de procesadores en función del tamaño del problema

Cocientes entre tiempos de ejecución obtenido con los diferentes usuarios con respecto al tmb
Autooptimización en sistemas homogéneos
37

Cocientes entre tiempos de ejecución obtenidos con los diferentes usuarios y métodos con respecto al tmb
Autooptimización en sistemas homogéneos
38

AUTOOPTIMIZACIÓN EN SISTEMAS HETEROGÉNEOS
39

Autooptimización en sistemas heterogéneos
Heterogéneos: agrupar elementos del sistema según características
similares no exactamente iguales.

Mayor dificultad construir modelo tiempo ejecución.

Buscar parámetros algorítmicos / min tº ejec

t(s, AP, SP)?

AP= d, p d=(d0,d1,…,dP-1) SP= Más complejos

Construir algoritmos heterogéneos

Diferentes posibilidades Desarrollo métodos (exactos y/o
aproximados de mapeo (asignar
procesos a procesadores))?

40

Distribución del trabajo y asignación de procesos a procesadores en un esquema de programación dinámica, en algoritmos heterogéneos (HeHo) (a) y homogéneos(HoHe) (b)?
Autooptimización en sistemas heterogéneos
41

Autooptimización en sistemas heterogéneos
42
Posibilidades de representación del árbol de asignación:

Árbol de asignación con 2
tipos de procesadores y p
procesos

Necesidad de limitar la
altura del mismo

Cada nodo lleva asociada
3 cotas: EET, LET, GET.

Uso de técnicas de
búsqueda en árboles para
optimizar el modelo de tº
ejecución

Autooptimización en sistemas heterogéneos
43

Desviación con respecto al tmb obtenido experimentalmente, de los tiempos obtenidos con diferentes métodos y usuarios en una combinación de TORC 1 17P4 + 1 Ath + 1 SPIII + 8 DPIII (a) y 1 Ath + 1 SPIII + 8 DPIII (b)?
a) b)?
Autooptimización en sistemas heterogéneos
44

Resultados de simulaciones diversas
Autooptimización en sistemas heterogéneos
45

METAHEURÍSTICAS EN LA AUTOOPIMIZACIÓN
46

Metaheurísticas en la autooptimización
OBJETIVO FINAL min tº ejec

Minimización analítica

Minimización numérica

Métodos exhaustivos

Métodos aproximados

Métodos heurísticos
47

Metaheurísticas en la autooptimización
48
Esquema General de las Metaheurísticas

Inicializar(S)?

while no se cumple CondiciondeFin(S) do

SS = ObtenerSubconjunto(S);

if |SS|>1 then
SS1= Combinar(SS);
else
SS1=SS;
end

SS2 = Mejorar(SS1);
S = IncluirSoluciones(SS2)?
end

Búsqueda Dispersa (particularización)?

Metaheurísticas en la autooptimización
Esquema de la tecnica de Búsqueda Dispersa (particularización)?

CrearConjuntoInicial S;
GenerarConjuntoReferencia RS;

while Convergencia no alcanzada do

Seleccionar elementos a combinar;

Combinar elementos seleccionados;

Mejorar elementos combinados;

ActualizarConjuntoReferencia RS con los elementos más
prometedores y los más dispersos

end?
49

Metaheurísticas en la autooptimización
Mapeo como un problema de optimización

Representación y codificación soluciones: (do,d1, …, dP-1)?
di = nº procesos asignados al procesador i

Gran cantidad de alternativas a la hora de instanciar el algoritmo:

50

Metaheurísticas en la autooptimización

Comparación entre las posibilidades de opciones de selección e inclusión. Porcentaje en que mejora la búsqueda dispersa respecto al backtracking con poda
Tiempos e iteraciones para diferentes métodos de selección e inclusión en el conjunto de referencia
51

Metaheurísticas en la autooptimización
Simulaciones para comparar Búsqueda dispersa y backtracking con poda

52

Metaheurísticas en la autooptimización
Pruebas en Kipling

53

Metaheurísticas en la autooptimización
Relación entre tiempos de decisión y modelado en una simulación concreta
54

CONCLUSIONES Y TRABAJOS FUTUROS
55

Conclusiones y Trabajos Futuros
Optimización Autooptimización

tº = f(s,AP,SP)?
Hipótesis investigación? +
Búsqueda óptimo

Métodos exactos (Búsqueda exhaustiva)?

Alternativas Métodos aproximados

Métodos metaheurísticos

56

Resultados generales en sistemas homogéneos(a), heterogéneos (b) y con el uso de metaheurísticas(c)?

Conclusiones y Trabajos Futuros
a) b)
57
a) b) c)?

Conclusiones y Trabajos Futuros
58
Aportaciones

VecPar04. Sistemas
homogéneos.

HeteroPar04,Parallel
Computing04. Sistemas
heterogéneos.

Para06, Maeb07.
Metaheurísticas.

Cluster07.

ICCS08.

Journal of
Supercomping 09.

Trabajos futuros

Mejorar el modelado el tiempo de
ejecución, sobre todo en
sistemas heterogéneos

Aplicación en diferentes esquemas
algorítmicos (divide & conquer,
master – slave, backtracking…)?

Metaheurísticas diversas (tabú,
temple simulado, géneticos …

Construcción de un entorno para
la prueba y evaluación de
metaheurísticas.